package com.mccken.practice.top100.Top_1$20.top_6;

import java.util.Stack;

/**
 * 42. 接雨水
 *
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-01 09:20
 **/
public class Trap {

	/*
	
	单调栈解法：
	构建一个单调递增栈(存储index)，遍历当前元素：
		当前元素 < 栈顶元素： 进栈
		当前元素 > 栈顶元素： 栈顶出栈，计算雨水面积，重复比对新的栈顶；当前元素进栈		
		
	 */
	public int trap(int[] height) {
		int n = height.length;
		int r = 0;
		Stack<Integer> stack = new Stack<>();

		for (int i = 0; i < n; i++) {
			if (stack.isEmpty()) {
				stack.push(i);
				continue;
			}

			// 栈里面有元素时

			// 当前元素 < 栈顶元素
			if (height[i] <= height[stack.peek()]) {
				stack.push(i);
				continue;
			}

			while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
				int rightIndex = i;
				// 本轮栈顶
				Integer mid = stack.pop();
				if (!stack.isEmpty()) {
					int leftIndex = stack.peek();
					int h = Math.min(height[rightIndex], height[leftIndex]) - height[mid];
					int w = rightIndex - leftIndex - 1;
					r += h * w;
				}
			}
			stack.push(i);
		}
		return r;
	}

	/**
	 * 单调栈
	 * 太多细节代码了，极容易犯错
	 *
	 * @param height
	 * @return
	 */
	public int trap2(int[] height) {

		int n = height.length;
		Stack<Integer> stack = new Stack<>();

		int res = 0;

		for (int i = 0; i < n; i++) {
			if (stack.isEmpty()) {
				stack.push(i);
				continue;
			}

			// 遍历到的值，小于栈顶元素
			if (height[stack.peek()] > height[i]) {
				stack.push(i);
				continue;
			}

			while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
				int indexPop = stack.pop();
				if (!stack.isEmpty()) {
					Integer indexTop = stack.peek();
					int h = Math.min(height[indexTop], height[i]) - height[indexPop];
					int w = i - indexTop - 1;
					res += h * w;
				}
			}
			stack.push(i);
		}
		return res;
	}

	// 双指针
	public int trap1(int[] height) {
		int n = height.length;
		int res = 0;

		int left = 0;
		int leftMax = 0;

		int right = n - 1;
		int rightMax = 0;

		while (left < right) {

			if (height[left] <= height[right]) {
				if (leftMax <= height[left]) {
					leftMax = height[left];
				}

				res += leftMax - height[left];
				left++;
			} else {
				if (rightMax <= height[right]) {
					rightMax = height[right];
				}
				res += rightMax - height[right];
				right--;
			}
		}
		return res;
	}

	public static void main(String[] args) {
		Trap trap = new Trap();
		System.out.println(trap.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
		System.out.println(trap.trap(new int[]{4, 2, 0, 3, 2, 5}));
		System.out.println(trap.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
		System.out.println(trap.trap(new int[]{0, 0, 3, 2, 2, 5, 4, 0, 9}));
	}

}
